数论总结

基础数论

扩展欧几里得算法 $\mathbf{exgcd}$

首先介绍一下贝祖定理。若 $a,b$ 是整数,那么 $a\cdot x+b\cdot y=\gcd(a,b)$一定有解。如果需要判断 $a\cdot x+b\cdot y=c$ 有没有解,可以直接判断 $c|\gcd(a,b)$可以用欧几里得算法求 $\gcd(a,b)$。但如果需要求出一组解,我们就必须对欧几里得算法进行扩展。考虑边界,欧几里得算法结束的条件是$b=0,a=\gcd(a,b)$ ,此时可以得到一组解 $x=1,y=0$。再考虑回溯是处理,每层我们都已知 $\gcd(b,a\bmod b)$ ,并且有一组解$x1,y1$ 使得 $b\cdot x1+(a\bmod b)\cdot y1=gcd$ 。我们知道,$a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor\cdot b$ 带入化简得$a\cdot y1+b\cdot (x1-\left\lfloor\frac{a}{b}\right\rfloor\cdot y1)=gcd$ 可以发现,$x=y1,y=x1-\left\lfloor\frac{a}{b}\right\rfloor\cdot y1$可以递归求解。时间复杂度为 $\Theta(\log_2 \max(a,b))$

乘法逆元 $\mathbf{inv}$

对于两个数 $a,p$ ,若有 $\gcd(a,p)=1$ ,那么一定
$\exists b\quad a\cdot b\equiv 1 \pmod{p}$ 。此时称 $b$ 为 $a$ 在模 $p$
意义下的逆元,记做 $a^{-1}=b$ 。计算乘法逆元,有多种方法。

费马小定理

费马小定理的内容是若 $\gcd(a,p)=1$ 则有 $a^p\equiv a \pmod{p}$
将其变形,可得 $a\cdot a^{p-2}\equiv 1 \pmod{p}$ 所以可以得到
$a^{-1}=a^{p-2}$ 可用快速幂求出。

扩展欧几里得

由定义可变形得到 $a\cdot a^{-1}=k\cdot p+1$ 移项可得 $a\cdot a^{-1}-k\cdot p=1$
与扩展欧几里得的标准形式一致。

线性递推计算

首先简单计算可得 $1^{-1}=1$ 。考虑对于 $\forall i$ ,如果 $i-1$
的逆元已经求出,可以线性求出。令 $p=k\cdot i+r$ ,则
$k=\left\lfloor\frac{p}{i}\right\rfloor,r=p \bmod i$ ,可得
$k\cdot i+r\equiv 0 \pmod{p}$ 经过代入整理得
$i^{-1}\equiv-\left\lfloor\frac{p}{i}\right\rfloor\cdot (p \bmod i)^{-1} \pmod{p}$
得出线性递推式。时间复杂度为 $\Theta(n)$ 。

阶乘递推计算

由逆元的定义可得 $n!^{-1}\equiv \frac{1}{n!} \pmod{p}$ 左右同乘 $n$
,化简得 $n!^{-1}\cdot n\equiv (n-1)!^{-1} \pmod{p}$ 得到递推式
$n!^{-1}\equiv \frac{(n-1)!^{-1}}{n} \pmod{p}$

中国剩余定理 $\mathbf{crt}$

中国剩余定理主要是为了解一种特殊的同余方程组。形如 $\begin{cases}
x\equiv a_1 \pmod{p_1}\\
x\equiv a_2 \pmod{p_2}\\
\cdots \\
x\equiv a_n \pmod{p_n}
\end{cases}$ 的式子。同时,式子满足 $\forall i,\forall j,i\neq j$
都有 $\gcd(p_i,p_j)=1$ 。考虑暴力做法,可以得到答案为下式
$k_1\cdot \frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_1}+k_2\cdot \frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_2}+\cdots +k_n\cdot \frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_n}$
且 $\forall i,i\leq n$ 满足
$k_i\cdot \frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_i}\bmod p_i=a_i$ 。设
$m_i=\frac{p_1\cdot p_2\cdot \cdots \cdot p_n}{p_i}$ 那么 $k_i\cdot m_i\equiv a_i \pmod{p_i}$
此时可以用逆元来求解 $k_i$ 最后求出答案。时间复杂度为 $\Theta(1)$ 。

扩展中国剩余定理 $\mathbf{excrt}$

如果中国剩余定理中的 $p_i$ 不满足 $\forall i,\forall j,i\neq j$ 都有
$\gcd(p_i,p_j)=1$ ,就不能使用中国剩余定理求解。考虑两两合并,下面方程组
$\begin{cases}
x\equiv a_1 \pmod{p_1}\\
x\equiv a_2 \pmod{p_2}\\
\end{cases}$ 可以化成 $p_1\cdot y+a_i=p_2\cdot z+a_2$
这个东西可以用扩展欧几里得合并。每次两两合并得出答案。时间复杂度
$\Theta(n\cdot \log_2 n)$ 。

大步小步算法 $\mathbf{BSGS}$

$BSGS$ 算法的目的是求解形如 $a^b\equiv c \pmod{p}$ ,其中 $\gcd(a,p)=1$
的同余方程。首先将 $b$ 写成 $k\cdot x+r$ 的形式。代入原式,得
$a^{k\cdot x}\equiv c\cdot a^r \pmod{p}$ 首先求出 $b$ 在 $[0,x-1]$
范围内右式的值,并储存。然后枚举所有可能的 $a$
,计算出左式的值,然后查询。时间复杂度为 $\Theta(\max(x,p/x))$ 可得
$x=\sqrt{p}$ 是最优。时间复杂度 $\Theta(\sqrt{p})$ 。

扩展大步小步算法 $\mathbf{exBSGS}$

如果在求解形如 $a^b\equiv c \pmod{p}$ 的同余方程时 $\gcd(a,p)\neq 1$
我们不能用 $BSGS$
来求。这个时候我们就必须换一种方法。首先把方程改写为等式 $a^b+k\cdot p=c$
发现此时的 $c$ 必须要是 $\gcd(a,p)$
的倍数,否则无解。不断在等式两边同时除以 $gcd(a,p)$ 直到
$\gcd(a,\frac{c}{\gcd(a,p)})=1$ ,此时式子满足 $BSGS$ 的求解条件,用
$BSGS$ 求解。

卢卡斯定理 $\mathbf{Lucas}$

$Lucas$ 定理用于求 $C_n^m\bmod p$ 的值。由二项式定理可知 $C_n^m$ 即为
$(x+1)^n$ 中 $x^m$ 的系数。对于式子
$(x+1)^{n_0}\cdot (x^p+1)^{n_1}\cdot (x^{p^2}+1)^{n_2}\cdot \cdots \cdot (x^{p^n}+1)^{n_k} \pmod{p}$
$C_{n_0}^{m_0}$ 即为 $(x+1)^n_0$ 中 $x^{b_0}$ 的系数, $C_{n_k}^{m_k}$
即为 $(x^{p^k}+1)^{n_k}$ 中 $x^{b_k\cdot p^k}$ 的系数,同理可得其余。因为
$\prod_{i=0}^k C_{n_i}^{m_i}\cdot x^{m_i\cdot p^i}=C_n^m\cdot x^m$ 所以可得
$C_n^m=\prod_{i=0}^k C_{n_i}^{m_i}$ 时间复杂度为 $\Theta(p\cdot \log_p n)$

素数合数

枚举判断

思路很简单,枚举 $[2,\left\lfloor\sqrt{n}\right\rfloor]$
范围内所有的数,判断是否是 $n$ 的因数。时间复杂度为 $\Theta(\sqrt{n})$

埃氏筛

埃氏筛的思想很简单,从 $2$
开始向后扫描,如果这个数是不是合数,那么把它的倍数全部标记为合数。时间复杂度为
$\Theta(n\cdot log_2 n)$ 。

线性筛

考虑优化埃氏筛。发现每个数都被它所有的质因数打上标记。可以通过使每个数都只被它最小的质因子筛去。将每个数的质数倍的数标记为合数(无论其本身是不是合数),这样可以保证每个数只会被自己最小的质因子筛去。

$\mathbf{Miller-Rabin}$

当我们需要判断一个数是否是质数时,我们需要 $\Theta(\sqrt{n})$
的时间判断。当这个数较大的时候,我们就不能使用枚举。考虑使用费马小定理。但当
$\gcd(a,b)=1$ 且 $a^p\equiv a \pmod{p}$ 时,不能得出 $p$
是质数的结论。这个时候我们引入二次探测。如果 $p$ 为质数,且 $0<x<p$
则方程 $x^2\equiv 1 \pmod{p}$ 的解为 $x=1$ 或 $x=p-1$ 。 $Miller-Rabin$
判断 $n$ 是否为质数的流程为:首先判断 $0,1,2$
和偶数。先随机取一个较小的质数 $p$ ,设 $s,t$ 满足 $2^s\cdot t=n-1$ 。算出
$p^t$ ,进行 $s$
次二次探测,每次进行平方,最后用费马小定理判断。多次取不同的 $p$
进行判断,如果全部通过,那么 $n$ 大概率是质数。算法时间复杂度为
$\Theta(p\cdot \log_2^3 n)$

函数

数论函数

数论函数是指这样一类函数:其定义域是正整数,值域是一个数集。定义两个数论函数的加法,为逐项相加,即
$(\mathbf{f+g})(n)=\mathbf{f}(n)+\mathbf{g}(n)$
。数乘,即一个数乘到一个数论函数上,定义为这个数和每一项都相乘,即
$(x\cdot \mathbf{f})(n)=x\cdot \mathbf{f}(n)$ 。

狄利克雷卷积

狄利克雷卷积是数论函数的一个运算。设 $\mathbf{h=f\times g}$ ,那么有
$\mathbf{h}(n)=\sum_{i|n} \mathbf{f}(i)\cdot \mathbf{g}(\frac{n}{i})$
它拥有以下性质:

  • $\mathbf{f\times g=g\times f}$
  • $\mathbf{(f\times g)\times h=f\times (g\times h)}$
  • $\mathbf{(f+g)\times h=f\times h+g\times h}$
  • $(x\times \mathbf{f})\times \mathbf{g}=x\times (\mathbf{f\times g})$
  • $\epsilon \times \mathbf{f}=\mathbf{f}$

欧拉函数

欧拉函数 $\phi(n)$ 是小于或等于 $n$ 的正整数中与 $n$
互质的数的数目。通式为 $\varphi(x)=x\cdot \prod_{i=1}^n (1-\frac{1}{p_i})$
其中 $p_1,p_2\cdots p_n$ 为 $x$
的质因子。处理可以用定义求解,也可以用埃氏筛和线性筛求解。

莫比乌斯函数

莫比乌斯函数的通式为 $\mu (n)=
\begin{cases}
1\quad n=1\\
(-1)^k\quad p_1\times p_2\times \cdots \times p_n\\
0\quad else
\end{cases}$ 莫比乌斯函数主要用于容斥原理。